package xyz.chaobei.leetcode.simple;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 买卖股票的最佳时机 II
 *
 * @see <a href='https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2zsx1/'></a>
 */
public class Solution {

    /**
     * <p>买卖股票的最佳时机,贪心算法，只要后一天的比前一天的要贵，就赚差价。
     * <p>author: <a href='mailto:maruichao52@gmail.com'>MRC</a>
     *
     * @return int
     * @since 2021/5/7
     **/
    public int maxProfit(int[] prices) {
        int max = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            if (prices[i] < prices[i + 1]) {
                max = max + prices[i + 1] - prices[i];
            }
        }
        return max;
    }

    /**
     * <p>旋转数组，通过临时数组解决。
     * <p>author: <a href='mailto:maruichao52@gmail.com'>MRC</a>
     *
     * @param nums
     * @param k    向右偏移位数
     * @return void
     * @since 2021/5/8
     **/
    public void rotate(int[] nums, int k) {

        int[] temp = new int[nums.length];

        for (int i = 0; i < nums.length; i++) {
            int index = (i + k) % nums.length;
            temp[index] = nums[i];
        }
        for (int i = 0; i < nums.length; i++) {
            nums[i] = temp[i];
        }
        System.out.println(Arrays.toString(nums));
    }

    /**
     * <p> 通过翻转数组实现
     * <p>author: <a href='mailto:maruichao52@gmail.com'>MRC</a>
     *
     * @param nums 翻转数组
     * @param k    移动次数
     * @return void
     * @since 2021/5/8
     **/
    public void rotate1(int[] nums, int k) {

        k %= nums.length;

        // 首先翻转全部
        this.rotates(nums, 0, nums.length - 1);
        this.rotates(nums, 0, k - 1);
        this.rotates(nums, k, nums.length - 1);

        System.out.println(Arrays.toString(nums));
    }

    /**
     * <p>翻转数组
     * <p>author: <a href='mailto:maruichao52@gmail.com'>MRC</a>
     *
     * @param nums  数组
     * @param start 起始位置
     * @param end   结束位置
     * @return void
     * @since 2021/5/8
     **/
    public void rotates(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start++] = nums[end];
            nums[end--] = temp;
        }
    }

    /**
     * <p>找出只有一个的元素
     * <p>author: <a href='mailto:maruichao52@gmail.com'>MRC</a>
     *
     * @param nums
     * @return int
     * @since 2021/5/12
     **/
    public int singleNumber(int[] nums) {
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            index = index ^ nums[i];
        }
        return index;
    }

    /**
     * <p>通过set集合实现，找出只要一个元素
     * <p>author: <a href='mailto:maruichao52@gmail.com'>MRC</a>
     *
     * @param nums
     * @return int
     * @since 2021/5/12
     **/
    public int singleNumber1(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            boolean save = set.add(nums[i]);
            if (!save) {
                set.remove(nums[i]);
            }
        }
        return (int) set.toArray()[0];
    }

    /**
     * <p>
     * <p>author: <a href='mailto:maruichao52@gmail.com'>MRC</a>
     *
     * @param nums 数组
     * @param k    移动位置
     * @return void
     * @since 2021/5/9
     **/
    public void rotate2(int[] nums, int k) {

        // 当前操作位置
        int index = 0;
        // 将要被覆盖的值。
        int temp = nums[index];

        // 防止原地打转
        boolean[] always = new boolean[nums.length];
        System.out.println(Arrays.toString(always));

        for (int i = 0; i < nums.length; i++) {

            index = (index + k) % nums.length;

            if (always[index]) {
                // 执行下一个元素
                index = (index + 1) % nums.length;
                temp = nums[index];
                i--;
            } else {
                always[index] = true;
                int nextVal = nums[index];
                nums[index] = temp;
                temp = nextVal;
            }
        }
        System.out.println(Arrays.toString(nums));
    }

    /**
     * <p>存在重复元素
     * <p>author: <a href='mailto:maruichao52@gmail.com'>MRC</a>
     * 通过循环判断。(暴力破解)
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(1)
     *
     * @return boolean
     * @since 2021/5/9
     **/
    public boolean containsDuplicate(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean containsDuplicate2(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                return true;
            }
        }
        return false;
    }

    public boolean containsDuplicate3(int[] nums) {

        Set<Integer> set = new HashSet<>();

        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) {
                return true;
            }
            set.add(nums[i]);
        }
        return false;
    }

}
